package 算法.leetcode.offer;

import 算法.leetcode.offer.base.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
 *
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *
 *     1
 *    / \
 *   2   2
 *  / \ / \
 * 3  4 4  3
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *
 *     1
 *    / \
 *   2   2
 *    \   \
 *    3    3
 *
 *  
 *
 * 示例 1：
 *
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * 示例 2：
 *
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 *
 * @author lchenglong
 * @date 2022/3/18
 */
public class Offer28 {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(4);
        list.add(3);
        TreeNode root = TreeNode.init(list);
        Offer28 instance = new Offer28();
        System.out.println(instance.isSymmetric(root));
    }
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        List<TreeNode> list;
        while (queue.size()!=0){
            list = new ArrayList<TreeNode>();
            int size = queue.size();
            for (int i=0;i<size;i++){
                TreeNode poll = queue.poll();
                list.add(poll);
                if (null != poll) {
                    queue.add(poll.left);
                    queue.add(poll.right);
                }
            }
            for (int i=0,j=list.size()-1;i<=j;i++,j--){
                if (list.get(i) == null&&list.get(j)!=null
                    ||list.get(i)!=null&&list.get(j)==null)
                    return false;
                if (list.get(i)!=null&&list.get(j)!=null&&list.get(i).val!=list.get(j).val)
                    return false;
            }
        }
        return true;
    }

    public boolean isSymmetric2(TreeNode root) {
        return root==null?true:recur(root.left,root.right);
    }

    boolean recur(TreeNode left,TreeNode right){
        if (left == null && right == null) return true;
        if (left== null||right==null||left.val!=right.val)return false;
        return recur(left.left,right.right)&&recur(left.right,right.left);
    }

}
